package _021_11_16

func _LCS(str1 string, str2 string) string {
	maxStr := ""
	subStr1 := getSubStr(str1)
	subStr2 := getSubStr(str2)
	for i := 0; i < len(subStr1); i++ {
		for j := 0; j < len(subStr2); j++ {
			if subStr1[i] == subStr2[j] {
				if len(maxStr) < len(subStr2[j]) {
					maxStr = subStr2[j]
				}
				break
			}
		}
	}
	return maxStr
}

func LCS(str1 string, str2 string) string {
	maxStr := ""
	subStr1 := getLineSubStr(str1)
	subStr2 := getLineSubStr(str2)
	for i := 0; i < len(subStr1); i++ {
		for j := 0; j < len(subStr2); j++ {
			if subStr1[i] == subStr2[j] {
				if len(maxStr) < len(subStr2[j]) {
					maxStr = subStr2[j]
				}
				break
			}
		}
	}
	return maxStr
}

func getSubStr(str string) []string {
	ret := make([]string, 0)
	ret = append(ret, "")
	for i := 0; i < len(str); i++ {
		size := len(ret)
		for j := 0; j < size; j++ {
			ret = append(ret, ret[j]+string(str[i]))
		}
	}
	return ret
}

func getLineSubStr(str string) []string {
	ret := make([]string, 0)
	for i := 0; i < len(str); i++ {
		for j := i + 1; j <= len(str); j++ {
			ret = append(ret, str[i:j])
		}
	}
	return ret
}
